|
A gain graph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a group ''G''. This means that, if an edge ''e'' in one direction has label ''g'' (a group element), then in the other direction it has label ''g'' −1. The label function φ therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edge ''e''. The group ''G'' is called the gain group, φ is the gain function, and the value φ(''e'') is the gain of ''e'' (in some indicated direction). A gain graph is a generalization of a signed graph, where the gain group ''G'' has only two elements. See Zaslavsky (1989, 1991). A gain should not be confused with a weight on an edge, whose value is independent of the orientation of the edge. ==Applications== Some reasons to be interested in gain graphs are their connections to network flow theory in combinatorial optimization, to geometry, and to physics. * The mathematics of a network with gains, or generalized network, is connected with the frame matroid of the gain graph. * Suppose we have some hyperplanes in ''R n'' given by equations of the form ''xj'' = ''g xi'' . The geometry of the hyperplanes can be treated by using the following gain graph: The vertex set is . There is an edge ''ij'' with gain ''g'' (in the direction from ''i'' to ''j'') for each hyperplane with equation ''xj = g xi'' . These hyperplanes are treated through the frame matroid of the gain graph (Zaslavsky 2003). * Or, suppose we have hyperplanes given by equations of the form ''xj'' = ''xi'' + ''g''. The geometry of these hyperplanes can be treated by using the gain graph with the same vertex set and an edge ''ij'' with gain ''g'' (in the direction from ''i'' to ''j'') for each hyperplane with equation ''xj'' = ''xi'' + ''g''. These hyperplanes are studied via the lift matroid of the gain graph (Zaslavsky 2003). * Suppose the gain group has an action on a set ''Q''. Assigning an element ''si'' of ''Q'' to each vertex gives a state of the gain graph. An edge is satisfied if, for each edge ''ij'' with gain ''g'' (in the direction from ''i'' to ''j''), the equation ''sj'' = ''si g'' is satisfied; otherwise it is frustrated. A state is ''satisfied'' if every edge is satisfied. In physics this corresponds to a ground state (a state of lowest energy), if such a state exists. An important problem in physics, especially in the theory of spin glasses, is to determine a state with the fewest frustrated edges. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「gain graph」の詳細全文を読む スポンサード リンク
|